\documentclass[lang=cn,11pt,a4paper]{article}
\usepackage{amsmath}
\usepackage{ctex}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{geometry}
\usepackage{caption}
\usepackage{listings}
\title{Theoretical Problem 2 of Numerical Analysis}
\author{庞竣元 \qquad 3200105017}
\date{}

\begin{document}

\maketitle

\noindent\uppercase\expandafter{\romannumeral1}. \\
{\it(1)}\quad By $Langrange formula$ we have 
\begin{equation*}
    \begin{aligned}
                 P_1(X)&=f_0l_0(x)+f_1l_1(x)  \\  
                        &=1\times(2-x)+\frac{1}{2}(x-1) 
                        &=-\frac{x}{2}+\frac{3}{2}
             \end{aligned}
\end{equation*}
And we have
\begin{equation*}
    f(x)-p_1(f;x)=\frac{f''(\xi (x))}{2}(x-x_0)(x-x_1)
\end{equation*}
Note that
\begin{equation*}
    f''(x)=\frac{2}{x^3}
\end{equation*}
Then we have
\begin{equation*}
    \begin{aligned}
        f''(\xi(x))=\xi^{-3}(x)&=\frac{f(x)-P_1(x)}{(x-x_0)(x-x_1)} \\
        &=\frac{\frac1x-(-\frac{x}{2}+\frac32)}{(x-1)(x-2)}=\frac{1}{2x}
    \end{aligned}
\end{equation*}
So
\begin{equation*}
    \xi(x)=\sqrt[3]{2x}
\end{equation*}
\noindent{\it(2)}
We can simply extend $\xi(x)$ from $(1,2)$ to $[1,2]$, since $\xi \nearrow$ in $[1,2]$, we can obtain
\begin{equation*}
    \max\xi(x)=\xi(2)=\sqrt[3]{4}\qquad\min\xi(x)=\xi(1)=\sqrt[3]{2}
\end{equation*}
Since $f''(\xi(x))=\xi^{-3}(x)=\frac1x \searrow$ in $[1,2]$, we can obtain
\begin{equation*}
    \max f''(\xi(x))=f''(\xi(1))=1
\end{equation*}

\noindent\uppercase\expandafter{\romannumeral2}. \\
Since $f_i \geq 0$, denote $u_i=\sqrt{f_i}$, let $q(x)$ be the unique polynomial in $\mathbb{P}_n$ satisfies that $q(x_i)=u_i$, then we can obtain $q(x)$ by $Lagrange formula$
\begin{equation*}
    q(x)= \sum_{k=0}^{n}u_k \prod_{i=0,i\not = k}^{n} \frac{x-x_i}{x_k-x_i}
\end{equation*}
Let $p(x)=q^2(x)$, we know that $p \in \mathbb{P}_{2n}^+$, and $p(x_i)=q^2(x_i)=f_i$, so $p$ is the polynomial that required, and we can express $p(x)$ by
\begin{equation*}
    p(x)= \left(\sum_{k=0}^{n}u_k \prod_{i=0,i\not = k}^{n} \frac{x-x_i}{x_k-x_i}\right)^2
\end{equation*}

\noindent\uppercase\expandafter{\romannumeral3}. \\
{\it(1)}\quad We use mathematical induction, when $n=0$, $\forall t \in \mathbb{R}, f[t]=f(t)=e^t$.
If when $n=k$, $\forall t \in \mathbb{R}$ we have
\begin{equation*}
    f[t,t+1,\dots,t+k]=\frac{(e-1)^k}{k!}e^t
\end{equation*}
Consider $n=k+1$, we can obtain $\forall t \in \mathbb{R}$
\begin{equation*}
\begin{aligned}
  f[t,t+1,\dots,t+k+1]&=\frac{f[t+1,t+2,\dots,t+1+k]-f[t,t+1,\dots,t+k]}{k+1}\\
  &=\frac{1}{k+1}[\frac{(e-1)^k}{k!}e^{t+1}-\frac{(e-1)^k}{k!}e^t]\\
  &=\frac{(e-1)^k}{k+1!}e^t(e-1)=\frac{(e-1)^{k+1}}{k+1!}e^t
\end{aligned}
\end{equation*}
So $\forall n \in \mathbb{N}, \forall t in \mathbb{R}, f[t,t+1,\dots,t+n]=\dfrac{(e-1)^n}{n!}e^t$\\
{\it(2)}\quad Let $t=0$, we have
\begin{equation*}
    f[0,1,\dots,n]=\frac{(e-1)^n}{n!}=\frac{f^{(n)}(\xi)}{n!}=\frac{e^\xi}{n!}
\end{equation*}
Which means $e^\xi=(e-1)^n$, $\xi=n\ln(e-1)>\dfrac{n}{2}$, $\xi$ is located right to the midpoint.

\noindent\uppercase\expandafter{\romannumeral4}. \\
{\it (1)}\quad We construct the divided difference table
\begin{table}[htbp]
    \centering
    \begin{tabular}{c|cccc}
         $0$ & $5$ & & &\\
        $1$ & $3$ & $-2$ & &\\
        $3$ & $5$ & $1$ & $1$ &\\
        $4$ & $12$ & $7$ & $2$ & $\dfrac{1}{4}$
    \end{tabular}
    \caption*{}
\end{table}\\
Then
\begin{equation*}
    p_3(f;x)=5-2x+x(x-1)+\frac{1}{4}x(x-1)(x-3)=\frac{1}{4}x^3-\frac{9}{4}x+5
\end{equation*}
{\it (2)}\quad $p'(x)=\dfrac{3}{4}x^2-\dfrac{9}{4}$, $p'(x)=0\Longleftrightarrow x=\pm \sqrt{3}$\\
Which means $p\nearrow$ in $[1,\sqrt{3}]$, $\searrow$ in $[\sqrt{3},3]$, then $x_{min}=\sqrt{3}\approx 1.732$

\noindent\uppercase\expandafter{\romannumeral5}. \\
{\it(1)}
\begin{table}[htbp]
    \centering
    \begin{tabular}{c|cccccc}
         $0$ & $0$ & & &\\
        $1$ & $1$ & $1$ & &\\
        $1$ & $1$ & $7$ & $6$ &\\
        $1$ & $1$ & $7$ & $21$ & $15$ \\
        $2$ & $128$ & $127$ & $120$ & $99$ & $42$ \\
        $2$ & $128$ & $448$ & $321$ & $201$ & $102$ & $30$
    \end{tabular}
    \caption*{}
\end{table}\\
Then we can obtain $f[0,1,1,1,2,2]=30$
{\it(2)}\quad $f^{(5)}(x)=2520x^2=30$, then $x=\dfrac{1}{2\sqrt{21}}\approx 0.109$

\noindent\uppercase\expandafter{\romannumeral6}. \\
{\it (1)}\quad We construct the devided differences table
\begin{table}[htbp]
    \centering
    \begin{tabular}{c|ccccc}
         $0$ & $1$ & & &\\
        $1$ & $2$ & $1$ & &\\
        $1$ & $2$ & $-1$ & $-2$ &\\
        $3$ & $0$ & $-1$ & $0$ & $\dfrac{2}{3}$ \\
        $3$ & $0$ & $0$ & $\dfrac{1}{2}$ & $\dfrac{1}{4}$ & $-\dfrac{5}{36}$
    \end{tabular}
    \caption*{}
\end{table}\\
Then we can obtain 
\begin{equation*}
    P(x)=1+x-2x(x-1)+\frac{2}{3}x(x-1)^2-\frac{5}{36}x(x-1)^2(x-3)
\end{equation*}
So we estimate $f(2)\approx P(2)=\dfrac{11}{18}$\\
{\it(2)}\quad By {\it Thm 2.37} we know that $\forall x \in [0,3],\ \exists \xi \in [0,3]\ s.t.$
\begin{equation*}
    f(x)-P(x)=\frac{f^{(5)}(\xi)}{5!}x(x-1)^2(x-3)^2
\end{equation*}
Therefore, $|f(2)-p(2)|\leq \dfrac{M}{60}$

\noindent\uppercase\expandafter{\romannumeral7}. \\
By {\it Thm 2.29}
\begin{gather*}
    f[x_0,x_1,\dots,x_k]=\frac{\Delta^kf_0}{k!h^k} \\
    \Delta^kf(x_0)=k!h^kf[x_0,x_1,\dots,x_k] \\
\end{gather*}
And
\begin{equation*}
\begin{aligned}
    \nabla^kf(x_0)&=\Delta^kf(x_{-k})\\
    &=k!h^kf[x_{-k},\dots,x_{-1},x_0]\\
    &=k!h^kf[x_{0},x_{-1},\dots,x_{-k}]
\end{aligned}
\end{equation*}

\noindent\uppercase\expandafter{\romannumeral8}. \\
We use mathematical induction, when $n=0$, $\dfrac{\partial f[x_0]}{\partial x_0}=\dfrac{\partial f(x_0)}{\partial x_0}=f'(x_0)=f[x_0,x_0]$\\
If when $n=k$ we have
\begin{equation*}
    \frac{\partial f[x_0,x_1,\dots,x_k]}{\partial x_0}=f[x_0,x_0,x_1,\dots,x_k]
\end{equation*}
Then we consider $n=k+1$:
\begin{equation*}
    \begin{aligned}
        \frac{\partial f[x_0,x_1,\dots,x_{k+1}]}{\partial x_0} &= \frac{\partial}{\partial x_0}\left(\frac{f[x_1,\dots,x_{k+1}]-f[x_0,\dots x_k]}{x_{k+1}-x_0} \right) \\
        &= \frac{-\frac{\partial f[x_0,\dots,x_k]}{\partial x_0}(x_{k+1}-x_0)+f[x_1,\dots,x_{k+1}]-f[x_0,\dots x_k]}{(x_{k+1}-x_0)^2}\\
        &= \frac{f[x_0,x_1,\dots,x_{k+1}]-f[x_0,x_0,\dots,x_k]}{(x_{k+1}-x_0)}\\
        &=f[x_0,x_0,x_1,\dots,x_{k+1}]
    \end{aligned}
\end{equation*}
Therefore, $\forall n \in \mathbb{N}$, $\dfrac{\partial f[x_0,x_1,\dots,x_n]}{\partial x_0}=f[x_0,x_0,x_1,\dots,x_n]$

\noindent\uppercase\expandafter{\romannumeral9}. \\ 
Denote $p(x)=a_0x^n+\dots+a_n$, let $x=\dfrac{(b-a)t+a+b}{2},\ t\in[-1,1]$\\
Consider $p(x)=q(t),q(t)=b_0t^n+\dots+b_n$, where $b_0=\dfrac{a_0(b-a)^n}{2^n}$\\
By {\it Col 2.47}
\begin{equation*}
    \max_{x\in [a,b]}|p(x)|=\max_{t\in[-1,1]}|q(t)|\geq \frac{b_0}{2^{n-1}}
\end{equation*}
Therefore
\begin{equation*}
    \min \max_{x\in [a,b]}|p(x)| = \frac{a_0(b-a)^n}{2^{2n-1}}
\end{equation*}
note:the conclusion may not be right, since the author didn't figure out how to attach.

\noindent\uppercase\expandafter{\romannumeral10}. \\ 
We already know that $||\hat{p}_n||_{\infty}=\dfrac{1}{|T_n(a)|}$, consider that $x_k=\cos(\dfrac{k\pi}{n}),k=0,1
\dots,n$, we have $\hat{p}_n(x_k)=\dfrac{(-1)^k}{T_n(a)}$\\
If $\exists p\ s.t. ||p||_\infty < \dfrac{1}{|T_n(a)|}$, denote $q=p-\hat{p}_n$, $q \in \mathbb{P}_n$ with $q(a)=0$, consider
\begin{equation*}
    q(x_k)=p(x_k)-\frac{(-1)^k}{T_n(a)}
\end{equation*}
We could easily find out that $q(x_k)q_(x_{k+1}) < 0$, so $\exists \xi_1,\dots,\xi_n \in [0,1]\ s.t. q(\xi_k)=0$\\
But $q(a)=0$ and $a>1$, then $q$ has at least $n+1$ roots, contradiction.\\
Therefore
\begin{equation*}
    ||p||_\infty \geq \frac{1}{|T_n(a)|} = ||\hat{p}_n||_{\infty}
\end{equation*}

\noindent\uppercase\expandafter{\romannumeral11}. \\ 
{\it (a)}\quad Trivially.\\
{\it (b)}
\begin{equation*}
    \sum_{k=0}^{n} b_{n,k}(t)=\sum_{k=0}^{n} \begin{pmatrix}n \\ k\end{pmatrix}t^k(1-t)^{n-k}=(t+1-t)^n=1
\end{equation*}
{\it (c)}
\begin{equation*}
    \begin{aligned}
        \sum_{k=0}^{n}kb_{n,k}(t)&=\sum_{k=0}^{n}k\begin{pmatrix}n \\ k\end{pmatrix}t^k(1-t)^{n-k}\\
        &=\sum_{k=1}^{n}nt\begin{pmatrix}n-1 \\ k-1\end{pmatrix}t^{k-1}(1-t)^{n-k}\\
        &=nt(t+1-t)^{n-1}=nt
    \end{aligned}
\end{equation*}
{\it (d)}
\begin{equation*}
    \begin{aligned}
        \sum_{k=0}^{n}k^2b_{n,k}(t)&=\sum_{k=0}^{n}k^2\begin{pmatrix}n \\ k\end{pmatrix}t^k(1-t)^{n-k}\\
        &=\sum_{k=2}^{n}n(n-1)t^2\begin{pmatrix}n-2 \\ k-2\end{pmatrix}t^{k-2}(1-t)^{n-k}+\sum_{k=1}^{n}nt\begin{pmatrix}n-1 \\ k-1\end{pmatrix}t^{k-1}(1-t)^{n-k}\\
        &=n(n-1)t^2(t+1-t)^n-2+nt(t+1-t)^n=n^2t^2+nt-nt^2
    \end{aligned}
\end{equation*}
Thus
\begin{equation*}
    \sum_{k=0}^{n}(k-nt)^2b_{n,k}(t)=nt(1-t)
\end{equation*}
\end{document}
